package com.leetcode.algorithm.y22.m06;

/**
 * 1143. 最长公共子序列
 * 
 * https://leetcode.cn/problems/longest-common-subsequence/
 * 
 * @author jie.deng
 *
 */
class Question1143Solution01 {

	public int longestCommonSubsequence(String text1, String text2) {
		int len1 = text1.length();
		int len2 = text2.length();

		// DP状态定义
		// dp[i][j]表示 text1[0...i] 和 text2[0...j] 最长公共子序列的长度
		int[][] dp = new int[len1 + 1][len2 + 1];
		// DP状态初始化
//		for (int i = 0; i < len1; i++) {
//			dp[i][0] = 0;
//		}
//		for (int j = 0; j < len2; j++) {
//			dp[0][j] = 0;
//		}

		// 状态转移方程
		for (int i = 1; i <= len1; i++) {
			for (int j = 1; j <= len2; j++) {
				if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}

		return dp[len1][len2];
	}

}